/*
 * Solution.cpp
 *
 *  Created on: 17/05/2011
 *      Author: daniel
 */

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include "Solution.h"

using namespace std;

/**
 * Crea una nueva solucion.
 * @param: un numero de ciudades.
 */
Solution::Solution(int n) {

	tour = new int[n];
	C = new double*[n];
	cityNumber = n; // Numero de Ciudades.
	cost = 0;
	numIter = 0;

	// Crea la matriz de costos.
	for (int i = 0; i < n; i++)
		C[i] = new double[n];

	// Inicializa los costos de la matriz en -1.
	for (int i = 0; i < n; i++)
		for (int j = i; j < n; j++)
			C[i][j] = 0;

	// Tour vacio.
	for (int i = 0; i < n; ++i)
		tour[i] = -1;

}

/**
 * Crea una nueva solucion.
 * @param: un numero de ciudades, una lista de ciudades.
 */
Solution::Solution(int n, vector<Node> ciudades) {

	tour = new int[n];
	C = new double*[n];
	cityNumber = n; // Numero de Ciudades.
	cost = 0;
	numIter = 0;

	// Crea la matriz de costos.
	for (int i = 0; i < n; i++)
		C[i] = new double[n];

	// Inicializa los costos de la matriz
	// con la distancia euclediana.
	for (int i = 0; i < n; i++)
		for (int j = 0/*i + 1*/; j < n; j++) {
			if (j < i)
				C[i][j] = 0;
			else
				C[i][j] = ciudades[i].distanciaEuc(ciudades[j]);
		}

	// Crea el tour.
	for (int i = 0; i < n; i++) {
		tour[i] = ciudades[i].nombre;
	}

	// Calcula el costo de la solucion.
	for (int i = 0; i < cityNumber - 1; i++)
		cost += getCost(i, i + 1);

	// Suma el costo de cerrar el ciclo.
	cost += getCost(cityNumber - 1, 0);
}

/**
 * Retorna un diferencial de costo.
 * @param: Dos posiciones en el arreglo.
 * @return: Un double que significa el costo diferencial.
 */
double Solution::costDifferential(int a, int b) {

	double diff = 0;

	double temp = min(a, b);
	b = max(a, b);
	a = temp;

	if (a == 0) {
		diff += getCost(a, cityNumber - 1);

	} else if (a > 0) {
		diff += getCost(a - 1, a);
	}

	if (b == a + 1) {
		diff += getCost(a, b);

	} else {
		diff += getCost(a, a + 1);
		diff += getCost(b - 1, b);
	}

	if (b == cityNumber - 1) {
		diff += getCost(0, b);

	} else if (b < cityNumber - 1) {
		diff += getCost(b, b + 1);
	}

	// Para no contar este costo dos veces.
	if (a == 0 && b == cityNumber - 1)
		diff -= getCost(0, cityNumber - 1);

	return diff;
}

/**
 * Busca la mejor solucion entre los vecinos
 * que no este en la Lista Tabu (LT), a menos
 * que la solucion sea mejor que la mejor
 * encontrada hasta el momento
 * @param: Lista de vecinos.
 * 		   Lista TABU (LT).
 * 		   Mejor Solucion encontrada
 *         hasta el momento (sMejor).
 * @return: Mejor solucion.
 */
int** Solution::bestSolution(vector<int> neighbors, Solution* sMejor, int **LT,
		int LTsize) {

	Solution* neighborSolution;

	double menorCosto = this->cost;
	int mini, maxi, minChosen, maxChosen;

	maxChosen = 0;
	minChosen = 0;

	/*Costos de todos los vecinos*/
	for (int i = 0; i < neighbors.size() - 2; i += 2) {

		mini = min(neighbors[i], neighbors[i + 1]);
		maxi = max(neighbors[i], neighbors[i + 1]);

		if (LT[mini][maxi] == 0) {
			neighborSolution = this->reverseWay(neighbors[i], neighbors[i + 1]);

			if (neighborSolution->cost < menorCosto) {
				*this = *neighborSolution->clone();
				menorCosto = this->cost;

				minChosen = mini;
				maxChosen = maxi;
			}
			delete neighborSolution;
		}
	}
	LT = updateLT(minChosen, maxChosen, this->cityNumber, LT, LTsize);
	return LT;
}

/**
 * Agrega una nueva ciudad al tour.
 */
int Solution::addCity(int city) {

	int i;
	for (i = 0; i < this->cityNumber; i++) {
		if (this->tour[i] == city)
			return -1;

		if (this->tour[i] == -1) {
			this->tour[i] = city;
			break;
		}
	}

	return i;
}

/**
 * Intercambia el contenido de las posiciones
 * a y b.
 * @param: int a, int b.
 */
Solution *Solution::swap(int a, int b) {

	Solution *s = this->clone();
	s->cost -= s->costDifferential(a, b);

	// Intercambia las ciudades.
	int temp = s->tour[a];
	s->tour[a] = s->tour[b];
	s->tour[b] = temp;

	s->cost += s->costDifferential(a, b);
	return s;
}

/**
 * Recalcula el costo de la solucion.
 * @return: El costo recalculado.
 */
double Solution::recomputeCost() {

	double c = 0.0;
	int i = 0;
	for (i = 0; i < cityNumber - 1; i++) {
		c += getCost(i, i + 1);
	}

	c += getCost(cityNumber - 1, 0);

	return c;
}

/**
 * Intercambia dos arcos del camino.
 * @param: dos enteros no consecutivos, correspondientes
 * 		   a la ciudad inicial de los arcos que se quieren
 * 		   intercambiar.
 */
Solution *Solution::flip(int a, int c) {

	Solution *s, *temp;

	temp = this->swap(a, c);
	s = temp->swap(a + 1, c + 1);
	delete (temp);

	return s;
}

/**
 * Retorna el costo de ir de la ciudad con la posicion
 * a en tour hasta la ciudad con la posicion b en tour.
 * @param: la posicion de la ciudad a y la de
 * 		   la ciudad b.
 */
double Solution::getCost(int a, int b) {

	if (a == b)
		return 0;

	// La matriz es triangular superior.
	if (tour[a] > tour[b]) {
		int temp = a;
		a = b;
		b = temp;
	}

	return C[tour[a] - 1][tour[b] - 1];
}

/**
 * Retorna el costo de ir de la ciudad a a la b.
 * @param: la ciudad a y la ciudad b.
 */
double Solution::getCostByCity(int a, int b) {

	if (a == b)
		return 0;

	// La matriz es triangular superior.
	if (a > b) {
		int temp = a;
		a = b;
		b = temp;
	}
	return C[a - 1][b - 1];
}

/*
 * Clona la solucion.
 * @return: una solucion.
 */
Solution *Solution::clone() {

	Solution *s = new Solution(this->cityNumber);

	// Copia las ciudades.
	for (int i = 0; i < this->cityNumber; i++)
		s->tour[i] = this->tour[i];

	// Copia la matriz de costos almacenados.
	for (int i = 0; i < this->cityNumber; i++) {
		for (int j = i; j < this->cityNumber; j++) {
			s->C[i][j] = this->C[i][j];
		}
	}

	s->iniCost = this->iniCost;
	s->cost = this->cost;
	s->cityNumber = this->cityNumber;

	return s;
}

/**
 * Imprime la solucion.
 */
void Solution::print() {

	cout << "[" << tour[0];

	for (int i = 1; i < cityNumber; i++)
		cout << ", " << tour[i];

	cout << "]" << endl;
	cout << "cost: " << cost << endl;
}

void Solution::printWithFormat() {

	cout << "Initial Cost: " << this->iniCost << endl;
	cout << "Final Cost: " << this->cost << endl;
	cout << "Iterations: " << this->numIter << endl;
	cout << "Relative Error: "
			<< (abs(this->iniCost - this->cost) / this->cost) * 100 << endl;
	cout << "Tour:" << endl;

	/*
	for (int i = 0; i < this->cityNumber; i++)
		cout << this->tour[i] << endl;
    */
}

void Solution::write(char *fileName) {

	ofstream output;
	output.open(fileName);

	output << "Initial Cost: " << this->iniCost << endl;
	output << "Final Cost: " << this->cost << endl;
	output << "Iterations: " << this->numIter << endl;
	output << "Relative Error: " << (abs(this->iniCost - this->cost)
			/ this->cost) * 100 << endl;
	output << "Tour:" << endl;

	for (int i = 0; i < this->cityNumber; i++)
		output << this->tour[i] << endl;

	output.close();
}

void Solution::reverse(int inicial, int final) {

	vector<int> auxTour;
	int auxPos[this->cityNumber];
	int i;

	/*Los que se mantienen igual*/
	for (i = 0; i < inicial; i++) {
		auxTour.push_back(this->tour[i]);
		auxPos[this->tour[i] - 1] = i;
	}
	/*Los que invierto*/
	for (int j = final; j >= inicial; j--) {
		auxTour.push_back(this->tour[j]);
		auxPos[this->tour[i] - 1] = i;
		i++;
	}
	/*Los otros que se quedan igual*/
	for (int j = final + 1; j < this->cityNumber; j++) {
		auxTour.push_back(this->tour[i]);
		auxPos[this->tour[i] - 1] = i;
		i++;
	}

	for (i = this->cityNumber - 1; i >= 0; i--) {

		int aux = auxTour.back();
		this->tour[i] = aux;
		auxTour.pop_back();

	}
}

Solution* Solution::reverseWay(int ini, int fin) {

	int inicial = min(ini, fin);
	int final = max(ini, fin);

	Solution *s = this->clone();

	s->cost -= s->costDifferential(inicial, final);

	s->reverse(inicial, final);

	s->cost += s->costDifferential(inicial, final);

	return s;
}
/**
 * Actualiza la lista Tabu LT
 * @param: Lista TABU (LT).
 * 		   posicion de la ciudad inicial
 * 		   posicion de la ciudad final
 * 		   numero de ciudades
 **/

int** Solution::updateLT(int min, int max, int size, int **LT, int LTsize) {

	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; ++j) {
			if (LT[i][j] > 0)
				LT[i][j]--;
		}
	}
	//Si se encontro alguna mejora
	if (max != 0 || min != 0)
		LT[min][max] = LTsize;

	return LT;
}

/*
 * Libera el espacio ocupado por una solucion.
 */
Solution::~Solution() {

	delete[] tour;

	for (int i = 0; i < cityNumber; i++)
		delete[] C[i];

	delete[] C;

}
